import random
def generate_move(board, player):
    # 检查是否是第一手（棋盘全空）
    if is_empty_board(board):
        return random_move(board)
    
    # 检查是否有立即获胜的位置
    winning_move = find_winning_move(board, player)
    if winning_move:
        return winning_move
    
    # 检查是否需要阻止对手获胜
    opponent = 3 - player  # 如果player是1则opponent是2，反之亦然
    blocking_move = find_winning_move(board, opponent)
    if blocking_move:
        return blocking_move
    
    # 如果没有紧急情况，选择最优的落子位置
    return find_best_move(board, player)

def is_empty_board(board):
    return all(board[i][j] == 0 for i in range(15) for j in range(15))

def random_move(board):
    empty_positions = [(i, j) for i in range(15) for j in range(15) if board[i][j] == 0]
    return random.choice(empty_positions)

def find_winning_move(board, player):
    # 检查所有空位置
    for i in range(15):
        for j in range(15):
            if board[i][j] != 0:
                continue
                
            # 临时落子
            board[i][j] = player
            
            # 检查是否获胜
            if check_win(board, i, j, player):
                board[i][j] = 0  # 恢复棋盘
                return (i, j)
            
            # 恢复棋盘
            board[i][j] = 0
    
    return None

def check_win(board, row, col, player):
    directions = [
        [(0, 1), (0, -1)],   # 水平
        [(1, 0), (-1, 0)],   # 垂直
        [(1, 1), (-1, -1)],  # 主对角线
        [(1, -1), (-1, 1)]   # 副对角线
    ]
    
    for dir_pair in directions:
        count = 1  # 包含当前位置
        
        # 检查两个相反的方向
        for dx, dy in dir_pair:
            x, y = row, col
            while True:
                x, y = x + dx, y + dy
                if not (0 <= x < 15 and 0 <= y < 15) or board[x][y] != player:
                    break
                count += 1
        
        if count >= 5:
            return True
    
    return False

def find_best_move(board, player):
    # 评分系统：统计每个位置周围的棋子分布
    best_score = -1
    best_moves = []
    
    for i in range(15):
        for j in range(15):
            if board[i][j] != 0:
                continue
            
            score = evaluate_position(board, i, j, player)
            
            if score > best_score:
                best_score = score
                best_moves = [(i, j)]
            elif score == best_score:
                best_moves.append((i, j))
    
    return random.choice(best_moves)

def evaluate_position(board, row, col, player):
    score = 0
    directions = [(0, 1), (1, 0), (1, 1), (1, -1)]
    
    for dx, dy in directions:
        # 统计连续的己方棋子
        count = 0
        x, y = row - dx, col - dy
        while 0 <= x < 15 and 0 <= y < 15 and board[x][y] == player:
            count += 1
            x, y = x - dx, y - dy
            
        x, y = row + dx, col + dy
        while 0 <= x < 15 and 0 <= y < 15 and board[x][y] == player:
            count += 1
            x, y = x + dx, y + dy
            
        # 根据连续棋子数量加分
        score += count * count
    
    return score
